#ifndef BTREE_H_
#define BTREE_H_
#include <algorithm>
#include <stack>
#include <list>
#include <assert.h>
#include <cstdint>

#include "table.h"
namespace bpt
{
    typedef int BTreeKeyType; // B树的key类型
    typedef size_t BTreeNodeIndexType; // B树节点的索引类型
    typedef uint8_t BTreeFlagType; // B树节点的标志位类型
    typedef BTreeFlagType BTreeNodeSizeType; // B树节点的大小类型
    constexpr BTreeFlagType UnusedKey = -1; // 用于标记未使用的key

    constexpr BTreeNodeSizeType BTreeMaxKeys = 4;
    constexpr BTreeNodeSizeType BTreeMaxChildren = BTreeMaxKeys + 1;
    constexpr BTreeFlagType BTreeNodeFlagIsLeaf = 1<<6;
    constexpr BTreeFlagType BTreeNodeTombstone = 1<<7;
    // BTreeNodeFlagSize必须能装下BTreeMaxKeys
    constexpr BTreeFlagType BTreeNodeFlagSize = 0b00011111;

    struct BTreeNode;

    union BTreeNodeData {
        BTreeNodeIndexType node;
        void* data;
    };

    struct BTreeMeta {
        BTreeNodeIndexType size;
    };

    struct BTreeNode {
        BTreeKeyType keys[BTreeMaxKeys];
        union BTreeNodeData children[BTreeMaxKeys+1];
        BTreeFlagType flag;
    };

    class BTree {
        struct BTreeResultSet {
            const BTree *btree_ = nullptr;
            BTreeKeyType to_ = UnusedKey;
            BTreeNodeSizeType index_ = 0;
            BTreeNodeIndexType node_ = -1;
            BTreeKeyType key = 0;
            void *data = nullptr;

            BTreeResultSet() = default;
            BTreeResultSet(const BTree *tree, BTreeNodeIndexType node, const BTreeNodeSizeType index, const BTreeKeyType to): btree_(tree), to_(to), index_(index), node_(node)
            {
                if (btree_!=nullptr && btree_->getNode(node) != nullptr)
                {
                    key = btree_->getNode(node)->keys[index_];
                    data = btree_->getNode(node)->children[index_].data;
                }
            }
            BTreeResultSet(const BTreeResultSet &other)
            {
                to_ = other.to_;
                index_ = other.index_;
                node_ = other.node_;
                key = other.key;
                data = other.data;
            }

            BTreeResultSet &operator++();
            BTreeResultSet &operator++(int);
            BTreeResultSet &operator+=(int n);

            inline bool operator==(const BTreeResultSet &other) const
            {
                return node_ == other.node_ && index_ == other.index_;
            }
            inline bool operator!=(const BTreeResultSet &other) const
            {
                return node_ != other.node_ || index_ != other.index_;
            }
            void next()
            {
                ++(*this);
            }

        };
    private:
        unsigned char *buffer_ = nullptr;
        size_t buffer_size_ = 0;
        struct BTreeMeta *meta_ = nullptr;

    public:
        ~BTree()
        {
            detach();
        }
        void attach(unsigned char *buffer, const size_t buffer_size) {
            if (buffer_size < sizeof(BTreeMeta)) {
                detach();
            }
            buffer_ = buffer;
            buffer_size_ = buffer_size;
            meta_ = reinterpret_cast<BTreeMeta*>(buffer_);
        }
        void detach() {
            buffer_ = nullptr;
            buffer_size_ = 0;
            meta_ = nullptr;
        }
        BTreeNodeIndexType getSize() const {
            return meta_!=nullptr ? meta_->size : 0;
        }
        void setSize(const BTreeNodeIndexType size) const
        {
            if (meta_!=nullptr) {
                // size必须单调递增，不能减少
                assert (meta_->size <= size);
                meta_->size = size;
            }
        }
        BTreeNode *getNode(const BTreeNodeIndexType index) const
        {
            if (index >= getSize() ||
                index == static_cast<BTreeNodeIndexType>(-1) ||
                index == 0 && getSize()>1 ||
                index * sizeof(BTreeNode) >= buffer_size_) {
                return nullptr;
            }
            return reinterpret_cast<BTreeNode*>(buffer_ + sizeof(BTreeMeta) + index * sizeof(BTreeNode));
        }
        BTreeNode *getRoot() const
        {
            return reinterpret_cast<BTreeNode*>(buffer_ + sizeof(BTreeMeta));
        }
        BTreeNodeIndexType getNodeIndex(const BTreeNode *node) const
        {
            if (buffer_ == nullptr || node == nullptr) {
                return -1; // 无效的索引
            }
            return (node - reinterpret_cast<BTreeNode*>(buffer_ + sizeof(BTreeMeta)));
        }
        BTreeNode *addNode(bool enableDeadNode=false) const;
        void *search(BTreeKeyType key, std::stack<BTreeNode*> *path=nullptr) const;
        BTreeResultSet search(BTreeKeyType key1, BTreeKeyType key2) const;
        void insert(BTreeKeyType key, void *data);
        std::pair<BTreeKeyType, BTreeNode *> split(BTreeNode* cursor) const;
        std::pair<BTreeKeyType, BTreeNode *> insertNode(BTreeNode *node, BTreeKeyType key, void *data) const;

        static inline BTreeNodeSizeType getNodeSize(const BTreeNode *node)
        {
            return node != nullptr ? (node->flag & BTreeNodeFlagSize) : 0;
        }
        static inline void setNodeSize(BTreeNode *node, const BTreeNodeSizeType size) {
            if (node != nullptr) {
                node->flag = (node->flag & ~BTreeNodeFlagSize) | (size & BTreeNodeFlagSize);
            }
        }
        static inline bool isLeafNode(const BTreeNode *node) {
            return node != nullptr && (node->flag & BTreeNodeFlagIsLeaf);
        }
        static inline void setLeafNode(BTreeNode *node, const bool is_leaf=true) {
            if (node != nullptr) {
                if (is_leaf) {
                    node->flag |= BTreeNodeFlagIsLeaf;
                } else {
                    node->flag &= ~BTreeNodeFlagIsLeaf;
                }
            }
        }
        static inline void clearNode(BTreeNode *node) {
            if (node != nullptr) {
                std::fill(std::begin(node->keys), std::end(node->keys), 0);
                BTreeNodeData data;
                data.data = nullptr;
                std::fill(std::begin(node->children), std::end(node->children), data);
                node->flag = 0;
            }
        }
        static inline bool isDeadNode(const BTreeNode *node) {
            return node != nullptr && (node->flag & BTreeNodeTombstone);
        }
        static inline void setNodeTombstone(BTreeNode *node, const bool is_tombstone=true) {
            if (node != nullptr) {
                if (is_tombstone) {
                    clearNode(node);
                    node->flag |= BTreeNodeTombstone;
                } else {
                    node->flag &= ~BTreeNodeTombstone;
                }
            }
        }
        BTreeNodeSizeType
        searchNode(const BTreeNode *parent, const BTreeNode *child) const;
        static BTreeNodeSizeType searchNode(const BTreeNode *parent, BTreeKeyType key);
        static bool removeNode(BTreeNode *node, BTreeKeyType key);
        void remove(BTreeKeyType key) const;
        bool combineNode(BTreeNode *parent, BTreeNode *child) const;
        void clear()
        {
            if (meta_ != nullptr) {
                meta_->size = 0;
                clearNode(getRoot());
            }
        }
        BTreeNode *getMinNode() const
        {
            if (buffer_ == nullptr || !getSize())
                return nullptr;
            BTreeNode *node = getRoot();
            while (node != nullptr && !isLeafNode(node)) {
                node = getNode(node->children[0].node);
            }
            return node;
        }
    };
}

namespace db {
class BTree
{
private:
    Table *table_ = nullptr;
public:
    BTree()
      : table_(nullptr)
    {}
    explicit BTree(Table *table): table_(table)
    {}
    inline void setTable(Table *table) { table_ = table; }
    inline Table *getTable() const { return table_; }
    inline unsigned int addBlock() const
    {
        unsigned int blockId = table_->allocate();
        BTreeBlock block;
        BufDesc *buf = kBuffer.borrow(table_->name_.c_str(), blockId);
        block.attach(buf->buffer);
        block.clear(1, blockId);
        kBuffer.releaseBuf(buf);
        return blockId;
    }
    inline unsigned int getRoot() const
    {
        if (table_ == nullptr) return 0;
        BufDesc *buf = kBuffer.borrow(table_->name_.c_str(), 0);
        if (buf == nullptr) return 0;
        SuperBlock super;
        super.attach(buf->buffer);
        unsigned int firstIndex = super.getFirstIndex();
        if (firstIndex == 0) {
            firstIndex = super.getFirst() ? super.getFirst() : addBlock();
            super.setFirstIndex(firstIndex);
            BufDesc *rootBuf = kBuffer.borrow(table_->name_.c_str(), firstIndex);
            Block block;
            block.attach(rootBuf->buffer);
            if (!super.getFirst()) {
                super.setFirst(firstIndex);
                block.setType(BLOCK_TYPE_DATA);
            }
            block.detach();
            kBuffer.releaseBuf(rootBuf);
        }
        super.detach();
        kBuffer.releaseBuf(buf);
        return firstIndex;
    }
    static inline bool isLeafNode(unsigned char *buffer)
    {
        if (buffer == nullptr) return false;
        auto header = reinterpret_cast<CommonHeader *>(buffer);
        return header->type == BLOCK_TYPE_DATA;
    }

    bool search(void *keyBuf, size_t len, std::vector<struct iovec> *iov, std::stack<unsigned short> *path=nullptr) const;
    void insert(const std::vector<struct iovec> &iov);
    void update(const std::vector<struct iovec> &iov);
    bool removeNode(DataBlock &cursor, void *keyBuf, size_t len);
    bool removeNode(BTreeBlock &cursor, void *keyBuf, size_t len);
    bool combineNode(BTreeBlock &parent, DataBlock &child, unsigned short keyIndex);
    bool combineNode(BTreeBlock &parent, BTreeBlock &child);
    void remove(void *keyBuf, size_t len);

    std::pair<struct iovec, unsigned int> splitNode(BTreeBlock &cursor);
    std::pair<struct iovec, unsigned int> splitNode(DataBlock &cursor);
    std::pair<struct iovec, unsigned int> insertNode(DataBlock &cursor, const std::vector<struct iovec> &iov);
    std::pair<struct iovec, unsigned int> insertNode(BTreeBlock &cursor, void *buf, size_t len, unsigned int child);
};
}

#endif // BTREE_H_
